#include <iostream>

using namespace std;

template<class T>
class Node {
public:
    T data;
    Node<T> *next;

    Node() {
        this->next = nullptr;
    }

    Node(T data) {
        this->next = nullptr;
        this->data = data;
    }
    
};

template<class T>
class LinkedList {
private:
    int length;
    Node<T> header;
public:
    LinkedList() {
        this->length = 0;
    }
    ~LinkedList() {
        Node<T> *cur_node = header.next;
        Node<T> *tmp_node;
        while (true) {
            if (!cur_node)
                break;
            tmp_node = cur_node->next;
            delete cur_node;
            cur_node = tmp_node;
        }
    }
    // 在头部插入结点
    void push_front(T data) {
        Node<T> *cur_node = new Node<T>(data);
        cur_node->next = header.next;
        header.next = cur_node;

        this->length++;
    }
    // 在尾部插入结点
    void push_back(T data) {
        Node<T> *cur_node = &header;

        for (int i = 0; i < length; i++) {
            cur_node = cur_node->next;
        }

        Node<T> *tmp_node = new Node<T>(data);
        cur_node->next = tmp_node;

        this->length++;
    }
    // 在指定位置插入结点,索引从0开始
    void insert(T data, int pos) {
        if (pos<0 || pos>length-1) {
            throw "Index out of range";
        }

        Node<T> *cur_node = &header;
        for (int i = 0; i < pos; i++) {
            cur_node = cur_node->next;
        }

        Node<T> *tmp_node = new Node<T>(data);
        tmp_node->next = cur_node->next;
        cur_node->next = tmp_node;

        this->length++;
    }
    // 删除指定位置的结点
    void remove(int pos) {
        if (pos<0 || pos>length-1) {
            throw "Index out of range";
        }

        Node<T> *cur_node = &header;
        for (int i = 0; i < pos; i++) {
            cur_node = cur_node->next;
        }

        Node<T> *tmp_node = cur_node->next;
        cur_node->next = cur_node->next->next;
        delete tmp_node;

        this->length--;
    }
    // 删除所有结点
    void remove_all() {
        Node<T> *cur_node = header.next;
        //header.next = nullptr;
        Node<T> *tmp_node;
        for (int i = 0; i < length - 1; i++) {
            tmp_node = cur_node;
            cur_node = cur_node->next;
            delete tmp_node;
        }
    }
    // 删除头部结点
    void pop_front() {
        if (empty())
            throw "LinkedList is empty";
        Node<T> *tmp_node = header.next;
        header.next = header.next->next;
        delete tmp_node;

        this->length--;
    }
    // 删除尾部结点
    void pop_back() {
        Node<T> *cur_node = &header;
        for (int i = 0; i < length - 1; i++) {
            cur_node = cur_node->next;
        }

        Node<T> *tmp_node = cur_node->next;
        cur_node->next = nullptr;
        delete tmp_node;
        this->length--;
    }
    // 查看头部结点的值,但不删除
    T &head() {
        if (empty())
            throw "LinkedList is empty";
        return header.next->data;

    }
    // 查看尾部结点的值,但不删除
    T &tail() {
        Node<T> *cur_node = &header;
        for (int i = 0; i < length; i++) {
            cur_node = cur_node->next;
        }
        return cur_node->data;
    }
    // 判断是否为空
    bool empty() {
        return header.next == nullptr;
    }
    // 返回链表长度
    int size() {
        return this->length;
    }
    // 遍历输出
    void traverse() {
        Node<T> *cur_node = &header;
        for (int i = 0; i < length; i++) {
            cur_node = cur_node->next;
            cout << cur_node->data << " ";
        }
        cout << endl;
    }
};